package 数据结构与算法.基础.单链表;

/*存在问题：
 * 添加英雄时没有考虑顺序，结果是按照添加顺序展示出来的，而不是序号顺序*/
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        SingleLinkedList sll = new SingleLinkedList();

//        sll.add(hero1);
//        sll.add(hero3);
//        sll.add(hero2);
//        sll.add(hero4);

        sll.addByOrder(hero3);
        sll.addByOrder(hero3);
        sll.addByOrder(hero2);
        sll.addByOrder(hero2);
        sll.addByOrder(hero1);
        sll.addByOrder(hero4);

        System.out.println("修改前");
        sll.show();

        HeroNode newHeroNode = new HeroNode(2, "小卢", "火麒麟");
        sll.update(newHeroNode);
        System.out.println("修改后");
        sll.show();

//        sll.delete(1);
//        sll.delete(2);
//        sll.delete(3);
//        sll.delete(4);
        System.out.println("删除后");
        sll.show();

        //统计结点个数
        System.out.println("有效的结点个数：" + getLength(sll.getHead()));

        /*-----------------------------------------------*/
        //查找单链表中倒数第k个结点【新浪面试题】
        /*1.编写一个方法getNodeByDescendOrder(HeroNode head, int index)
        接收head结点和index(表示倒数第index个结点)
        * 2.调用getLength方法，得到链表总长size
        * 3.再次遍历，从第一个开始遍历(size-index)个,每找到一个结点，temp就后移一次，循环结束temp即为所找结点。
        * 4.找到就返回结点，没有找到返回null
        */
        System.out.println("=======");
        System.out.println("查找单链表中倒数第k个结点【新浪面试题】");
        HeroNode node = getNodeByDescendOrder(sll.getHead(), 1);
        System.out.println("倒数第k个结点为：" + node);

        //单链表的反转【腾讯面试题】
        System.out.println("=======");
        System.out.println("单链表的反转【腾讯面试题】");
        reverseList(sll.getHead());
        sll.show();

    }

    public static void reverseList(HeroNode head){
        if(head.next==null||head.next.next==null){
            System.out.println("空链表或只有一个结点，反转后仍为本身");
            return;
        }
        HeroNode temp = head.next;
        HeroNode next = null;//指向当前结点的下一个结点
        HeroNode reverseHead = new HeroNode(0,"","");
        while (temp!= null) {
            next=temp.next;//保留当前结点的下一个结点，同时起到了仿覆盖作用
            temp.next=reverseHead.next;//将temp的下一个结点指向新链表的最前端
            reverseHead.next=temp;//将temp结点挪到新链表上
            temp=next;//利用next赋值为下一个结点，相当于后移
        }
        head.next=reverseHead.next;
    }

    public static HeroNode getNodeByDescendOrder(HeroNode head, int index) {
        //链表为空，返回null
        if (head.next == null) {
            return null;
        }
        //第一次遍历
        int size = getLength(head);
        //第二次遍历
        //index校验
        if (index <= 0 || index > size) {
            return null;
        }
        HeroNode temp = head.next;//定义辅助变量
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;//temp后移，移到我们需要找的位置
        }
        return temp;
    }

    //获取单链表结点的个数,带头结点的不统计头结点
    public static int getLength(HeroNode head) {
        int length = 0;
        if (head.next == null) {//空链表
            return 0;
        }
        HeroNode temp = head.next;//没有统计头结点
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }
}

//定义一个HeroNode类，每一个HeroNode的对象就是一个结点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个结点

    //构造器
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    //为了显示方便查看，重写toString
    public String toString() {
        return "HeroNode[no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
    }
}

//定义一个SingleLinkedList类，管理单链表
class SingleLinkedList {
    //初始化头节点
    private HeroNode head = new HeroNode(0, " ", " ");

    public HeroNode getHead() {
        return head;
    }

    //添加结点到单链表
    /*不考虑结点编号顺序时
     * 1.找到当前链表的最后一个结点
     * 2.将该结点的next指向要添加的结点*/
    public void add(HeroNode hn) {
        //因为头节点不能动，创建一个辅助结点
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //将最后一个结点指向新结点
        temp.next = hn;
    }

    //按顺序加入
    public void addByOrder(HeroNode hn) {
        HeroNode temp = head;//辅助变量
        boolean flag = false;//标志位，确定编号是否存在

        while (true) {
            if (temp.next == null) {//说明temp已经到达链表的最后
                break;
            }
            if (temp.next.no > hn.no) {//说明已经找到位置，在temp后面插入
                break;
            } else if (temp.next.no == hn.no) {//说明编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;
        }

        //判断标志位
        if (flag == true) {
            System.out.printf("待插入英雄编号:%d已经存在\n", hn.no);
        } else {
            //插入到链表中,交换next
            hn.next = temp.next;
            temp.next = hn;
        }
    }

    //修改结点信息，但是编号不能修改，否则相当于添加新的信息
    public void update(HeroNode newHeroNode) {
        //先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无信息");
        }
        //若链表不为空，根据no编号去找需要修改的结点
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            //已经遍历完整个链表,但没有找到编号
            if (temp == null) {
                break;
            }
            //找到了对应结点
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            //没有找到就继续后移
            temp = temp.next;
        }
        //用标志位flag来确定是没有找到还是已经找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.printf("没有找到编号%d的结点\n", newHeroNode.no);
        }
    }

    //删除结点
    /*1.head不能动，借助辅助变量temp找到待删除结点的前一个结点
     * 2.比较时需要用temp.next.no与待删除结点.no进行比较*/
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //已经遍历完整个链表
            if (temp == null) {
                break;
            }
            //找到了待删除结点的前一个结点
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            //没有找到就继续后移
            temp = temp.next;
        }
        //根据标志位进行删除操作
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("没有找到待删除编号为%d的结点\n", no);
        }
    }

    //显示链表
    public void show() {
        //因为头节点不能动，创建一个辅助结点
        HeroNode temp = head.next;//不要头结点，直接指向头结点指向的结点。

        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无数据");
            return;
        }

        while (true) {
            //判断结点是否走到最后
            if (temp == null) {
                break;
            }
            //没有走到最后，就把每个结点信息输出来
            //因为已经事先重写了toString方法，直接输出即可
            System.out.println(temp);
            temp = temp.next;
        }

    }

}